package effizienz;
import effizienz.Land.Stadt;
import javax.swing.JFrame;

/**Der Travelling Sales Man sucht für eine Menge von Städten diejenige
 * Reihenfolge, die bei einer Rundfahrt am kürzesten ist.
 */
public class TSM {
  public static void main(String[] args){
    //GUI-Zeugs
    JFrame f=new JFrame("Travelling Salesman");
    f.setSize(600, 600);
    f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    Land land=new Land(12);
    f.getContentPane().add(land);
    f.setVisible(true);
    //optimiere die Rundreise des Landes
    tsm(land);
    System.out.println("Fertig.");
  }

  /**Untersucht die Städte eines Landes und findet eine möglichst gute
   * Rundreise.
   * @param land das Land, dessen Städte in eine möglichst gute Reihenfolge
   *   gebracht werden.
   */
  public static void tsm(Land land){
    //Daten holen
    Stadt[] reise=land.getAktuelleRundReise();
    System.out.println("Strecke="+land.rundReiseStrecke());
    //bringe die Elemente von reise in beste Reihenfolge
    permute(reise, 1, land);
  }

  public static void permute(Stadt[] reise, int ab, Land land){
    if(ab>=reise.length){
      double r=land.rundReiseStrecke(reise);
      double a=land.rundReiseStrecke();
      if(r<a){
        land.setRundReise(reise.clone());
        System.out.println("bessere Strecke="+r);
      }
    } else
      for(int i=ab; i<reise.length; ++i){
        Stadt hilf=reise[ab]; reise[ab]=reise[i]; reise[i]=hilf;
        permute(reise, ab+1,land);
        hilf=reise[ab]; reise[ab]=reise[i]; reise[i]=hilf;
      }
  }
}
